Think of the solution to this question in a constructive way.
To produce a postal code, there are 6 tasks to do, task
#1 - pick first letter
#2 - pick first number
#3 - pick second letter
#4 - pick second number
#5 - pick 3rd letter
#6 - pick 3rd number
These tasks are performed in sequence and since for each choice of 1st letter we have a different postal code, attached to each fist letter in the number of ways to pick the remaining 5 symbols
Next, we pick the first number and attached to this choice is the number of ways to pick the remaining 4 symbols, etc. (We have seen this before. Where?)
This is an illustration of the Product Rule of Counting
The Product Rule of Counting
Suppose a procedure involves a sequence of k stages. Let ni=# of ways to do stage i, Suppose also that stage i must be done before stage i+1 1≤2≤k−1.
Then the total number of ways the procedure can be done is
n=n,n2⋅⋯⋅nk−1⋅nk
Returning to the postal code problem,
the number of ways to pick a letter is 26 and the number of ways to pick a digit is 10 so the total number of possible postal codes is
n=26⋅10⋅26⋅10⋅26⋅10=17,576,000
Of course this is not the number of useable postal codes. Eg 0∅0−∅0∅ is possible but not practical
Examples
Let A,B be finite sets. ∣A∣=n,∣B∣=m
How many functions are there from A to B.
For each element a∈A there are m choices for the image f(a)∈B. There are n different elements of A so the total number of functions from A to B is
N=n times m⋅m⋅⋯⋅m=mn
How many bit strings of length n are there?
We can consider a bit string of length n as a function f:{1,3,⋯,n}→{0,1}
where f(k)= kth bit in the string
By example 1
# of bit strings of length n=2n
The product rule can be phrased in terms of the cartesian product of sets
let A1,⋯,Ak be the finite sets
let A=A1×A2×⋯×Ak=\set(a1,a2,⋯,ak)∣ai∈Ai1≤i≤k
Then ∣A∣=∣A1∣⋅∣A2∣⋯∣Ak∣
So far we have looked at the procedure that are done sequentially, where the number of ways to do i+1 steps of the procedure depends on the number of ways to do i steps
Some procedures are disjoint and for these types we use the sum rule of counting
The Sum Rule of Counting
Suppose a procedure cen be broken down into k different sub-procedures (or cases) that are disjoint from each other. Suppose sub-procedure i can be done in ni ways, 1≤i≤k.
Then the procedure can be done in n=n1+n2+⋯+nk ways.
Examples
A library has 24 math books and 73 cookbooks. How many ways can a student pick a math book or a cookbook?
Answer=24+73=9 ways to pick a matchbook or a cookbook.
Compare this to: How many way can a student pick a math book and a cookbook?
Answer =24⋅73=1,752 ways.
Some problems use a combination of the Sum and Product Rules to obtain an answer
Examples
A password for a certain system can be either 6,7 or 8 characters long
the first character must be a letter and the last character must be a number The other characters can be letters on numbers (a number = decimal digit) How many possible passwords are there?
Solution We have 3 disjoint cases Case 1 6 symbols → do in n1, ways Case 2 7 symbols → do in n2 ways Case 3 8 symbols. → do in n3 ways
This example is an application of the Inclusion-Exclusion Principle to counting
How many bit strings of length 9 start witt 2 zeros or end with one?
Let A= set of bit strings of length 9 that start with 2 zeros.
∣A∣=27 since we put 2 zeros at the start in one way and put the other 7 bits in 27 ways.
B= set of bit strings of length 9 that end with one ∣B∣=28
Now the set of bit strings that start with 2 zeros or end with 1 one is A∪B and
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=27+28−∣A∩B∣
But ∣A∩B∣= # bit stings of length 9 with 2 zeros at start and one at the end =26
∴∣A∪B∣=27+28−26=26(2+4−1)=5⋅26=10⋅25=320.
Four different coins can be placed in 3 different cans in how many ways if
i) there are no restrictions
ii) can#1 has at least 1 coin in it?
Solution
i)4coins→3cans This can be thought of as the number of functions from a set of 4 objects (coins) to a set of 3 objects (cans)
∴ # of ways =34=81
ii) To calculate the # of ways can #1 gets at least one coin consider that of all the ways to place the coins, there are 2 disjoint cases
{ can#1 has no coins } or { can #1 has some coins} ie; at least one
and81=∣case#1∣+∣case#2∣
Now if can#1 has no coins, then we are placing 4 coins in 2 cans in 24=16 ways
∴ # of ways can #1 has at least 1 coin
=81−16=65 ways
Further Examples
A binary operation on a set A is a mapping ∗:A×A→A
That is ∗ takes two elements a,b∈A and combines them to get an element c of A. If (a,b)∈A×A then
∗(a,b)=c iff a∗b=c
To determine the number of binary operations on a finite set we note that if ∣A∣=n, then ∣A×A∣=n2
Thus the number of binary operations on A is the number of functions from a set of size n2 to a set of size n,
Thus the number of binary operations is n(n2)
For example, if A={a,b,c,d}, then the number of distinct binary operations is
232=416=4,294,967,296
Let A be a set of ndistinct elements, A={a1,a2,⋯,an}\
Let f:A→A be 1−1 and onto. How many such f are there?
Since f(1−1,f(ai)=f(aj) if i=j
Now for f(a1) we have x choices of the image
Once this image is used, it cant be used again since f is 1−1
Thus for f(a2) we have n−1 choices, f(a3) has x−2 choices, etc, until for f(an) we have only one choice.
Thus # of 1−1 onto maps of A={a1,a2,…,an} is
N=n(x−1)(x−2)⋯2⋅1=x!
Such a function f:A→A,1−1 onto is called a permutation
We study permutations of a more general kind later
Tree Diagrams
For some complicated counting problems, it can be useful to use a tree diagram
A tree consists of a root, a number of branches leaving the root, and perhaps, additional branches leaving the ends of each branch, and so on.
For a counting problem we use a branch to represent each possible choice in a stage of a process
Example How many bit strings of length 5 do not have 2 consecutive ones?
Each branch represents a bit so there is 5 bits
also note, therefore 25−13=32−13=19 bit strings have at least two consecutive 1's.
The Pigeon Hole Principle (Dirichlet Drawer Principle)
If k+1 or more objects are placed into k boxes, then there is at least one box containing 2 or more objects
Proof Suppose none of the boxed contains more than one object. Then the total number of objects is at most k. This contradicts the hypothesis that we have at least k+1(>k) objects
Trivial Example a collection of 367 people must have at least 2 people with the same birthday.
Non-Trivial Example For every integer n, ∃d∈Z such that d⋅n has only zeros and ones in its decimal representation
Proof Without loss of generality, we may assume that n>0. If not apply what follows to −x>0, to get −dn with only zeros and ones in ito expansion
For n>0, consider the set S of x+1 different
numbers: 1,11,111,1111,⋯,n+1digits11⋯1
Since there are only n possible remainders when an integer is divided by n, two of these numbers have the same remainder when divided by n. Let these numbers be a,b where a>b.
Then a≡b(modn)
and hence a−b≡0(modn)
Thus a−b is a multiple of n,a−b=d⋅x and a−b has only zeros and ones in its decimal representation
a−ba−b===111111111111110000
Generalized Pigeon Hole Principle
If N objects are placed into k boxes, then there is at least one box containing ⌈RN⌉ objects.
Proof Suppose the conclusion is false
Then none of the k boxes contains more than ⌈kN⌉−1 objects
Then the total number of objects is at most
k{⌈kN⌉−1}<k{(kN+1)−1}=N
Example Assume that in a group of 6 people, each pair of individuals consists of either 2 friends or 2 enemies. Show that there are either three mutual friends on three mutual enemies in the group
Solution Let the people be called A,B,C,D,E,F. Consider the person called A. The other five people are either friends of A or enemies of A. One of these two sets will have at least 3=⌈257⌉ people in it
Suppose there are at least 3 friends of A in the other 5 Take any 3 other people. If 2 these are friends, then these two and A make three mutual friends. If none of these 3 people are friends, then they are 3 mutual enemies
This argument can be mirrored if A has at least 3 mutual enemies, to complete the proof
Permutations
A permutation on a set of n objects is a re-ordering of the elements. Here we are assuming that the objects are distinct, ie, we can tell them apart, and certainly that their order matters
The number of ways to permute n distinct objects is n!=n(n−1)⋯2⋅1 where by convention, 0!=1
Suppose now we have n distinct objects and we went to select r of these objects, in order, How many different ways can we do this?
This is called an r-permutation:
Picking r distinct objects from n distinct objects where the order of choice matters.
The number of ways to do this in denoted P(n,r) and
P(n,r)=n(n−1)⋯(n−r+1)(nPr)↑r terms here
Proof We use the product rule of counting to show this fact
For the first selection we have n choices, Fo the second selection we bare n−1 choices,
How many different way can gold, silver and bronze medals be awarded for a race with 8 contestants, no ties allowed.
SolutionP(8,3)=8⋅7⋅6=336 ways
How many ways can the letters ABCDEFGHIJ be rearranged so that the letters DEF are together in that order?
Solution Consider DEF as one letter. Then we must find the number of permutations of 8 letters. This can be done
8!=40,320 ways
Travelling Salesman Problem. a salesman must visit 10 different addresses. If she can visit each address in any order, how many different routes are possible?
Ans 10!=3,628,800 ways.
If we now want to find the minimum distance route, we must compute 3,628,800 different distances and compare. This type of problem, routing, is a factorial growth complexity problem and very important and hard to deal with
Combinations
Suppose now we want to select r distinct objects from a collection of n distinct objects, where the order of selection does not matter
That is we want to chooser objects form n objects
The number of ways this cen be done is called C(n,r) or more commonly
(nr)=n choose r=nCr
We have
Proof The number of ways of selecting. r object where the order matters is P(x,r)=x(x−1)⋯(x−r+1)
Alternately, we could select the r objects first, in C(x,r) ways and for each such choice of r elements we have r! ways to list them as 1st choice, 2nd choice,..., rth choice.
Thus
P(n,r)=r!C(n,r) by the product rule
Thus
(nr)=(C(n,r)=r!P(n,r)=r!n(n−1)⋯(n−r+1)
Note
(nr)=r!(x−r)!n! This is valid for n,r positive integers
(nr)=r!n(n−1)⋯(n−r+1) is valid for n∈Rr positive integer
By convention
(n0)=1,∀n,(0r)=0,r=1,2,⋯
also we have
(n1)=n(nn)=1,∀n,∀n∈Z+
The numbers (nr),r=0,1,⋯,n are called the binomial coefficients and we will consider this aspect of them later
Note also
(nr) is the number of subsets of size r in a set with n element. If S a set, ∣S∣=n, then
∣P(S)∣=2n
And P(S) is the union of all subsets with 0 element, all subsets with 1 element, ..., all subsets with n elements, with (n0)=1,(nn)=1, we have by the
∣P(S)∣=(n0)+(n1)+(n2)+⋯+(nn−1)+(nn)=2n
We have just given a combinatorial
(20proof of the following algebraic result
Theorem
∑r=0n(nr)=2n
We can also give a combinatorial proof of the following fact or an algebraic proof
Theorem (nr)=(nn−r)
Proof
(nn−r)=(n−r)!(n−(n−r))!n!=(n−r)!r!n!=(nr)
alternate
Let S be a set of x elements. Let A⊆S have r elements.
Then Aˉ=S−A has n−r elements.
Thus for every subset of size r, there is exactly one of size n−r
∴(nn−r)=(nr).
Examples
How many five and hands can be dealt from a standard playing deck of 52 cards?
ans (525)=5⋅4⋅3⋅2⋅152⋅51⋅50⋅49⋅48=52⋅51⋅4.9⋅20=2,598,960
How many five card hands can be dealt from a standard playing deck that contain exactly 3 hearts?
Solution This is a 2 stage process.
Fist we pick 3 hearts out of 13 hearts in (133)=3.2.113.12.11=286 ways
Then we pick 2 cards out of the remaining 39 cards in (392)=2.139.38=741 ways
Thus total # of ways is 286×741=211,926
How many five card hands can be dealt from a standard playing deck that contain at least 3 hearts
Solution There are 3 cases to consider
3 hearts case 1
4 hearts case 2
5 hearts case 3
Thus at least 3 hearts can be done in 211926+27885+1287=241,098 ways.
How many bit strings of length 12 contain
a) exactly 3 i's?
b) at most 3 i's ?
c) at least 3 1's ?
d) equal number of zeros \& ones?
Solution
a) Consider the problem this way. Imagine a bit string of length 12 to be 12 slots that must be filled with zeros or I's. We have exactly 3 ones to put in the 12 slots. Once we have dore this we put zeros in all the rest. Thus we have (123)=3,2,112⋅11⋅10=220 ways
(23) to place the three ones in the bit string.
b) At most 3 means 0,1,2, or 3 ones.
There are 4 cases and using the sum rule we see that there are
(12a)+(121)+(122)+(123) ways to have at most 3 ones in the bit string of length 12 ii, 1+12+66+220=299 bit stings with at most 3 ones
c) The number of bit strings with at least 3 ones is the total number of bit strings minus those with 0,1 or 2 ones
Thus we have 212−{(120)+(121)+(122)}=4096−(1+12+66)
=4017
bit strings of length 12 with at least 3 ones. (24)
d) An equal number of ones and zeros means 6 ones 10 we candor this in
(126)=6.5⋅4⋅32112⋅11⋅10⋅9⋅8⋅7=11⋅12⋅7=924
Exercise Do example 4 a) -d) for bit strings of length 11 .
Recommended Exercises
th ROSEN:-
Ch 6.1P416→#1−26,34,35,50,51
6,2p427#15,166.3p435→±1−6,11,12,18−20,30.
(25)
P417#7,8,9
How many different 3 letter initials can people have?
26⋅26⋅26=263=17,576
3 letter initials with norepeated letters?
26⋅25⋅24=15,600
3 letter initials starting with A ?
A⋅26⋅26=262=676.
p 427#15
(26)
a) Show that if 5 integers are chosen from the first 8 positive integers ie, from {1,2,3,4,5,6,7,8} there must be a pair of these integers with a sum equal to 9.
b) Is the con clusion of a) true if 4 integers are chosen instead of 5?
a) Group the numbers in pairs
{1,8},{2,7},{3,6},{4,5}
Pick 5 numbers, By P.H.P. we must pick both numbers in one of these sets Q∈D